/*
 created by coderon
29 September 2020
这个存储结构是顺序表，即数组
*/

#include <stdio.h>
class Sequential
{
private:
    int array[1000];
    int tail = -1; //最后一个元素下标

    //这些函数不足为外人道也
private:
    int Partition(int first, int last);  //快速排序所用到的函数
    void quickSort(int first, int last); //快速排序

public:
    Sequential() {}
    Sequential(int array[], int len);
    ~Sequential();
    void Insert(int insert); //插入给定值

    void Print();                            //输出数组
    void Delete(int deleted);                //删除给定的值
    int Find(int find, int first, int last); //查找所给值得下标
    void Reverse();                          //逆置函数
};

Sequential::Sequential(int array[], int len)
{
    int i;
    for (i = 0; i < len; i++)
    {
        this->array[i] = array[i];
        tail = i;
    }

    quickSort(0, tail);
}

Sequential::~Sequential()
{
}

void Sequential::Insert(int insert)
{
    array[++tail] = insert;
    quickSort(0, tail);
}

// int array[7] = {23, 13, 35, 6, 19, 50, 28};
// // 一次快排的函数
int Sequential::Partition(int first, int last)
{
    //为什么要多搞一个参数来接，因为first和last要递归传下去
    int i = first;
    int j = last;
    int temp;
    while (i < j)
    {
        // 右边扫描
        while (i < j && array[i] <= array[j])
            j--;
        if (i < j)
        {
            temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
        // 左边扫描
        while (i < j && array[i] <= array[j])
            i++;
        if (i < j)
        {
            temp = array[j];
            array[j] = array[i];
            array[i] = temp;
        }
    }
    return i;
}
//快排函数，注意这里的last是指最后一个元素的下标
void Sequential::quickSort(int first, int last)
{
    int i = Partition(first, last);
    if (i - 1 > first)
        quickSort(first, i - 1);
    if (i + 1 < last)
        quickSort(i + 1, last);
    return;
    /* 你还可以这样写，更加简洁一些 */
    // if (first >= last) return;
    // int i = Partition(first, last);
    // quickSort(first, i - 1);
    // quickSort(i + 1, last);
}

//将对象的数组打印出去
void Sequential::Print()
{
    for (int i = 0; i < tail + 1; i++)
    {
        printf("%d   ", array[i]);
    }
    printf("\n");
}
//删除指定值得元素              (原理是找一个删一个)
void Sequential::Delete(int deleted)
{
    int location = Find(deleted, 0, tail);
    // printf(" loaction = %d      tail = %d\n", location, tail);
    while (location != -1)
    {
        int front = location;
        int next = location + 1;
        for (int i = 0; i < (tail - location); i++, front++, next++)
        {
            array[front] = array[next];
        }
        array[tail] = 0; //做好收尾工作
        tail--;
        // Print();
        location = Find(deleted, 0, tail);
        // printf(" loaction = %d      tail = %d\n", location, tail);
    }
}

//查找指定元素，并且返回指定元素        (这里使用二分查找，因为构造函数已经对数组进行了排序)
int Sequential::Find(int find, int first, int last)
{

    if (first > last)
        return -1;
    else
    {
        int i = (last + first) / 2;
        int tmp = array[i];
        if (find > tmp)
            return Find(find, i + 1, last);
        else if (find < tmp)
            return Find(find, 0, i - 1);
        else
            return i;
    }
}
//逆置函数
void Sequential::Reverse()
{
    int len = tail + 1;
    if (len == -1 || len == 0)
        return;

    int front = 0;
    int back = tail;
    int tmp;
    while (front < back)
    {
        tmp = array[front];
        array[front] = array[back];
        array[back] = tmp;
        front++;
        back--;
    }
    return;
}
